import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * Created by zhourh on 2018/7/31.
 *
 * 给定一个N叉树，返回其节点值的后序遍历。
 *
 */
public class NAryTreePostorderTraversal {

    public static void main(String[] args) {
        Node root = new Node();
        root.val = 1;
        Node node2 = new Node();
        node2.val = 10;
        Node node3 = new Node();
        node3.val = 3;
        Node node4 = new Node();
        node4.val = 5;
        Node node5 = new Node();
        node5.val = 0;
        Node node6 = new Node();
        node6.val = 6;
        List<Node> level2 = new ArrayList<>();
        level2.add(node2);
        level2.add(node3);
        level2.add(node4);
        root.children = level2;
        List<Node> level3 = new ArrayList<>();
        level3.add(node5);
        level3.add(node6);
        node2.children = level3;

        System.out.println(new NAryTreePostorderTraversal().postorder(root));

    }

    public List<Integer> postorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Stack<Node> opStack = new Stack<>();
        opStack.push(root);
        while (!opStack.empty()) {
            Node node = opStack.pop();
            ans.add(node.val);
            if (node.children != null) {
                for (Node n : node.children) {
                    opStack.push(n);
                }
            }
        }

        Collections.reverse(ans);
        return ans;
    }
}
